package day11;

import java.util.Arrays;

public class 快速排序 {

    public static int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        QuickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void QuickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int index  = middleNum(array, left, right);
        swap(array,index ,left);
        int i = partition(array, left,right);
        QuickSort(array, left, i - 1);
        QuickSort(array, i + 1, right);
    }

    /**
     * 三数取中法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int middleNum(int[] array, int left, int right) {
        //中间位置的下标
        int mid = left + ((right - left) >> 1);
        //怎么拿到这个下标对应的中间数字呢
        if(array[left] < array[right]){
            if(array[left] > array[mid]){
                return left;
            }else if (array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[left] < array[mid]){
                return left;
            }else if (array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }


    /**
     * 前后指针法
     */
    private static int partition2(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }


    /**
     * 挖坑法
     *
     * @param array
     * @param left
     * @param right
     */
    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] < tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    /**
     * Hoare法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */

    public static int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array, left, right);
        }
        //进行交换
        swap(array, left, i);
        return left;
    }

    public static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2, 7, 1, 6};
        System.out.println(Arrays.toString(sortArray(array)));
//        partition2(array,0,array.length - 1);
//        System.out.println(Arrays.toString(array));
    }
}
